package atividades.huffman;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 
 * @author Dennis Fernandes
 *
 */
public class Algoritmo {

	private String texto;
	private ArrayList<String> passos;
	private int numeroBytesSemHuffman;
	private int numeroBytesComHuffman;
	
	/**
	 * 
	 */
	public void iniciar() {
		passos = new ArrayList<String>();
		List<Letra> lista = separarTexto();
		lista = ordenar(lista);
		List<Arvore> listaNodes = retornaNode(lista);
		Letra[] listaBackup = lista.toArray(new Letra[0]);
		
		int contador = lista.size() - 1;
		Arvore arvoreBackup = null;
		while(contador > 0){
			salvarPasso(listaNodes);
			Arvore aux1 = listaNodes.remove(contador);
			Arvore aux2 = listaNodes.remove(contador - 1);
			Letra aux3 = new Letra(aux2.getLetra().getValor() + aux1.getLetra().getValor(),
									aux1.getLetra().getQuantidade() + aux2.getLetra().getQuantidade());
			
			Arvore novaArvore = new Arvore();
			novaArvore.setLetra(aux3);
			novaArvore.setFilho_esquerda(aux2);
			novaArvore.setFilho_direita(aux1);
			listaNodes.add(novaArvore);
			listaNodes = ordenarNode(listaNodes);
			contador--;
		}
		
		arvoreBackup = listaNodes.get(0);
		
		numeroBytesSemHuffman = 0;
		for(Letra letra : listaBackup){
			int caminho = retornaNumero(arvoreBackup, letra.getValor(), 0);
			int valor = letra.getQuantidade() * caminho;
			numeroBytesSemHuffman +=  valor;
		}
	}
	
	private void salvarPasso(List<Arvore> listaArvores) {
		String passo = "";
		for (Arvore node : listaArvores) {
			passo += (node.getLetra() + " ");
		}
		passos.add(passo);
	}

	private List<Arvore> retornaNode(List<Letra> lista) {
		List<Arvore> retorno = new ArrayList<Arvore>();
		for (Letra letra : lista) {
			retorno.add(new Arvore(letra));
		}
		return retorno;
	}

	private int retornaNumero(Arvore arvore, String letra, int contador){
		if(arvore == null)
			return -1;
		if(arvore.getLetra().getValor().equals(letra))
			return contador;
		int retorno = -1;
		retorno = retornaNumero(arvore.getFilho_direita(), letra, contador + 1);
		if(retorno > -1)
			return retorno;
		return retornaNumero(arvore.getFilho_esquerda(), letra, contador + 1);
	}

	
	/**
	 * 
	 */
	private List<Letra> ordenar(List<Letra> lista){
		List<Letra> listaAux = new ArrayList<Letra>();
		for(Letra letra : lista){
			int pos = -1;
			for(int i=0; i<listaAux.size(); i++){
				if(letra.getQuantidade() > listaAux.get(i).getQuantidade()){
					pos = i;
					break;
				}
			}
			if(pos > -1){
				listaAux.add(pos, letra);
			} else {
				listaAux.add(letra);
			}
		}
		return listaAux;
	}
	
	private List<Arvore> ordenarNode(List<Arvore> lista){
		List<Arvore> listaAux = new ArrayList<Arvore>();
		for(Arvore arvore : lista){
			int pos = -1;
			for(int i=0; i<listaAux.size(); i++){
				if(arvore.getLetra().getQuantidade() > listaAux.get(i).getLetra().getQuantidade()){
					pos = i;
					break;
				}
			}
			if(pos > -1){
				listaAux.add(pos, arvore);
			} else {
				listaAux.add(arvore);
			}
		}
		return listaAux;
	}

	/**
	 * 
	 * @return
	 */
	private List<Letra> separarTexto(){
		Map<String, Integer> mapQuantidade = new HashMap<String, Integer>();
		List<Letra> retorno = new ArrayList<Letra>();
		for(int i=0; i < texto.length(); i++){
			String charAux = String.valueOf(texto.charAt(i));
			if(mapQuantidade.containsKey(charAux)){
				int novoQtd = mapQuantidade.get(charAux) + 1;
				mapQuantidade.put(charAux, novoQtd);
			} else {
				mapQuantidade.put(charAux, 1);
			}
		}		
		for(String key : mapQuantidade.keySet()){
			Letra aux = new Letra();
			aux.setValor( key + "" );
			aux.setQuantidade( mapQuantidade.get(key) );
			retorno.add(aux);
		}
		return retorno;
	}
	
	
	
	
	
	
	
	
	
	
	/* Gets e Sets */
	
	/**
	 * @return the texto
	 */
	public String getTexto() {
		return texto;
	}
	/**
	 * @param texto the texto to set
	 */
	public void setTexto(String texto) {
		//this.texto = texto;
		this.numeroBytesComHuffman = 8 * texto.length();
		this.texto = texto;
	}
	/**
	 * @return the passos
	 */
	public ArrayList<String> getPassos() {
		return passos;
	}
	/**
	 * @param passos the passos to set
	 */
	public void setPassos(ArrayList<String> passos) {
		this.passos = passos;
	}
	/**
	 * @return the numeroBytesSemHuffman
	 */
	public int getNumeroBytesSemHuffman() {
		return numeroBytesSemHuffman;
	}
	/**
	 * @param numeroBytesSemHuffman the numeroBytesSemHuffman to set
	 */
	public void setNumeroBytesSemHuffman(int numeroBytesSemHuffman) {
		this.numeroBytesSemHuffman = numeroBytesSemHuffman;
	}
	/**
	 * @return the numeroBytesComHuffman
	 */
	public int getNumeroBytesComHuffman() {
		return numeroBytesComHuffman;
	}
	/**
	 * @param numeroBytesComHuffman the numeroBytesComHuffman to set
	 */
	public void setNumeroBytesComHuffman(int numeroBytesComHuffman) {
		this.numeroBytesComHuffman = numeroBytesComHuffman;
	}
}
